package com.example.sudoku;

import java.util.*;

public class SudokuDLX extends AbstractSudokuSolver {
    /*
        入口参数：board 现有棋盘 newBoard：待复制的棋盘
        目的：二维数组的传递
        无返回值
    */
    public static void copyBoard(int[][] board, int[][] newBoard) {
        for (int i = 0; i < SaveBoard.return_size(); i ++) {
            for (int j = 0; j <SaveBoard.return_size() ; j ++) {
                newBoard[i][j] = board[i][j];
            }
        }
    }

    /*
        入口参数 suduku 初始棋盘
        目的：通过初始棋盘已有数据，排除通过精确覆盖问题进行建模建立二维数组中不可能出现的情况
        返回值：排除不可能情况的数组
    */
    private int[][] makeExactCoverGrid(int[][] sudoku) {
        int[][] R = sudokuExactCover();
        for (int i = 1; i <= S; i++) {
            for (int j = 1; j <= S; j++) {
                int n = sudoku[i - 1][j - 1];
                if (n != 0) {
                    for (int num = 1; num <= S; num++) {
                        if (num != n) {
                            // 排除不可能情况
                            Arrays.fill(R[getIdx(i, j, num)], 0);
                        }
                    }
                }
            }
        }
        return R;
    }

     /*
        目的：进行建模，将数独问题转换为一个精确覆盖问题
        每个格子都要填入数字 1到81列，表示数独中9*9=81个格子是否填入了数字。如果是，则选取的01行在该01列上为1
        每一行都要有1~9填入 81+1到81*2列，每9列就代表数独中的一行，如果该行有某个数字，则其对应的列上为1
        每一列都要有1~9填入m81*2+1到81*3列，每9列就代表数独中的一列
        每一宫都要有1~9填入81*3+1到81*4列，每9列就代表数独中的一宫
        每一个格子共有9中可能，则整个棋盘共有9*9*9钟情况
        所以需建立一个9*9*9与9*9*4的二维数组进行记录，以便于后续dancinglinks的建立
        返回值：所构建的二维数组
    */
    private int[][] sudokuExactCover() {
        int[][] R = new int[SaveBoard.return_size()*SaveBoard.return_size()*SaveBoard.return_size()][SaveBoard.return_board() * 4];

        int hBase = 0;

        // 格子与数
        for (int r = 1; r <= S; r++) {
            for (int c = 1; c <= S; c++, hBase++) {
                for (int n = 1; n <= S; n++) {
                    R[getIdx(r, c, n)][hBase] = 1;
                }
            }
        }

        // 数与行
        for (int r = 1; r <= S; r++) {
            for (int n = 1; n <= S; n++, hBase++) {
                for (int c1 = 1; c1 <= S; c1++) {
                    R[getIdx(r, c1, n)][hBase] = 1;

                }
            }
        }

        // 数与列
        for (int c = 1; c <= S; c++) {
            for (int n = 1; n <= S; n++, hBase++) {
                for (int r1 = 1; r1 <= S; r1++) {
                    R[getIdx(r1, c, n)][hBase] = 1;
                }
            }
        }

        // 数与宫格
        for (int br = 1; br <= S; br += side) {
            for (int bc = 1; bc <= S; bc += side) {
                for (int n = 1; n <= S; n++, hBase++) {
                    for (int rDelta = 0; rDelta < side; rDelta++) {
                        for (int cDelta = 0; cDelta < side; cDelta++) {
                            R[getIdx(br + rDelta, bc + cDelta, n)][hBase] = 1;
                        }
                    }
                }
            }
        }

        return R;
    }

    /*
        获取id:(例如)
        23 =        （3-1）*9 + 5    第 3 行第 5 列填入了数字
        106= 81   + （3-1）*9 + 7    第 3 行填入了7
        205= 81*2 + （5-1）*9 + 7    第 5 列填入了7
        259= 81*3 + （2-1）*9 + 7    第 2 宫填入了7
    */
    private int getIdx(int row, int col, int num) {
        return (row - 1) * S * S + (col - 1) * S + (num - 1);
    }

    /*
        目的：对初始数独棋盘进行计算，得出正确答案与最终解法个数
        入口参数：suduku 初始棋盘
        无返回值
    */
    protected void runSolver(int[][] sudoku) {
        // 将数独问题转换为一个精确覆盖问题，建立二维数组的矩阵
        int[][] cover = makeExactCoverGrid(sudoku);
        // 将该矩阵转换为跳舞链
        DancingLinks dlx = new DancingLinks(cover, new SudokuHandler(S));
        // 计算数独答案
        dlx.runSolver();
        if (dlx.solutionBoard != null) {
            this.solutionBoard = new int[SaveBoard.return_size()][SaveBoard.return_size()];
            copyBoard(dlx.solutionBoard, this.solutionBoard);
        }
        // solutions为该矩阵解法
        solutions = dlx.solutions;
    }
}
